package com.zlk.algorithm.dataStructure.graph.shortestPath;
import com.zlk.algorithm.dataStructure.graph.impl.Edge;
import com.zlk.algorithm.dataStructure.graph.impl.Node;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @program: algorithm
 * @ClassName Dijkstra
 * @description:最短路径算法
 * @author: slfang
 * @create: 2024-03-25 09:37
 * @Version 1.0
 **/
public class Dijkstra {

    /**
     *https://www.bilibili.com/video/BV1zz4y1m7Nq/?spm_id_from=333.337.search-card.all.click&vd_source=8d72483edcfecc46d5b590a803601a2b
     * 思路：前提无负权边
     * 每次找到最小距离的节点，发散设置to的距离值，然后将当前最小的节点锁住
     * 1、记录form 到所有节点的距离都是无穷大
     * 2、
     *
     *
     */

    //todo  加强堆实现
    public HashMap<Node,Integer> dijkstra(Node from){
        //定义
        //选中的点
        HashSet<Node> selectedNodes = new HashSet<>();
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(from,0);
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null){
            //  原始点  ->  minNode(跳转点)   最小距离distance
            int distance = distanceMap.get(minNode);
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode)) {
                    distanceMap.put(toNode, distance + edge.weight);
                } else { // toNode
                    distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    /**
     * 查找不在已经确定了的节点，剩下最小的距离的节点
     * @param distanceMap
     * @param touchedNodes
     */
    public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            int distance = entry.getValue();
            if (!touchedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }

}
